home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / win / general / atree.exe / lha / ATREE.DOC < prev    next >
Text File  |  1991-07-05  |  58KB  |  1,613 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.                           An Implementation of Adaptive Logic Networks
  13.                           ~~ ~~~~~~~~~~~~~~ ~~ ~~~~~~~~ ~~~~~ ~~~~~~~~
  14.                                   
  15.                             copyright W.W. Armstrong and Andrew Dwelly
  16.                                                      November 11, 1990
  17.  
  18.                                      bug-fixes and initial port to DOS
  19.                                                      Rolf Manderschied
  20.                                                         April 15, 1991
  21.  
  22.                                          revised for Microsoft Windows
  23.                                                       Monroe M. Thomas
  24.                                                           May 31, 1991
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72. 1     Introduction
  73. ~     ~~~~~~~~~~~~
  74.  
  75. The Windows dynamic link library atree.dll contains an implementation of
  76. an unconventional kind of learning algorithm for adaptive logic
  77. networks[Arms], which can be used in place of the backpropagation
  78. algorithm for multilayer feedforward artificial neural networks [Hech],
  79. [Rume].
  80.  
  81. The ability of a logic network to learn or adapt to produce an arbitrary
  82. boolean function specified by some empirical "training" data is certainly
  83. important for the success of the method, but there is another property of
  84. logic networks which is also essential.  It is the ability to generalize
  85. their responses to new inputs, presented after training is completed.  The
  86. successful generalization properties of these logic networks are based on
  87. the observation, backed up by a theory [Boch], that trees of two-input
  88. logic gates of types AND, OR, LEFT, and RIGHT are very insensitive to
  89. changes of their inputs.
  90.  
  91. Some experiments on handwritten numeral recognition and satellite image
  92. classification have been successfully carried out. [Arms3, Arms4].  Recent
  93. experiments have shown this algorithm to learn quickly on some problems 
  94. requiring learning of integer or continuous-valued functions where 
  95. backpropagation has reportedly led to long training times; and it 
  96. functions very well on boolean data [Arms5].
  97.  
  98. At the present time, only limited comparisons have been made with the 
  99. conventional approach to neurocomputing, so the claims necessarily have to 
  100. be muted.  This situation should rapidly be overcome as users of this 
  101. software (or improved variants of it yet to come) begin experimentation.  
  102. However one property of these networks in comparison to others is an 
  103. absolute, and will become apparent to computer scientists just by 
  104. examining the basic architecture of the networks.  Namely, when special 
  105. hardware is available, this technique, because it is based on
  106. combinational logic circuits of limited depth (e. g. 10 to 20 propagation
  107. delays), can potentially offer far greater execution speeds than other
  108. techniques which depend on floating point multiplications, additions, and
  109. computation of sigmoidal functions.
  110.  
  111. A description of the class of learning algorithms and their hardware
  112. realizations can be found in [Arms, Arms2], but we will briefly introduce
  113. the concepts here. An atree (Adaptive TREE) is a binary tree with nodes of
  114. two types: (1) adaptive elements, and (2) leaves.  Each element can
  115. operate as an AND, OR, LEFT, or RIGHT gate, depending on its state.  The
  116. state is determined by two counters which change only during training.
  117. The leaf nodes of the tree serve only to collect the inputs to the subtree
  118. of elements.  Each one takes its input bit from a boolean input vector or
  119. from the vector consisting of the complemented bits of the boolean input
  120. vector.  The tree produces a single bit as its output.
  121.  
  122.  
  123.                                     -1-
  124.  
  125. Despite the apparent limitation to boolean data, simple table-lookups permit
  126. representing non-boolean input values (integers or reals for example) as bit
  127. vectors, and these representations are concatenated and complemented to form
  128. the inputs at the leaves of the tree.  For computing non-boolean outputs,
  129. several trees are used in parallel to produce a vector of bits representing
  130. the output value.
  131.  
  132. This software contains everything needed for a programmer with knowledge of
  133. C and Windows 3.x to create, train, evaluate, and print out adaptive logic
  134. networks. It has been written for clarity rather than speed in the hope that
  135. it will aid the user in understanding the algorithms involved.  The
  136. intention was to try make this version faster than variants of the
  137. backpropagation algorithm for learning, and to offer much faster evaluation
  138. of learned functions than the standard approach given the same
  139. general-purpose computing hardware.  Users of the software are requested to
  140. provide some feedback on this point to the authors.
  141.  
  142. This software also includes a language "lf" that allows a non-programmer
  143. to conduct experiments using atrees, as well as a number of
  144. demonstrations.
  145.  
  146. A version of this software which is both faster and contains a more
  147. effective learning algorithm is planned for the near future.
  148.                                   Y
  149.                                   │
  150.                           ┌───────┴───────┐
  151.                           │  Random Walk  │
  152.                           │    Decoder    │
  153.                           └───────┬───────┘
  154.                           ┌───────┴───────┐
  155.                           │ Output Vector │
  156.                           └┬─────────────┬┘
  157.                            │             │
  158.     Trees - one per       (O)           (O)
  159.     output bit             │             │
  160.                      ┌─────┴────┐      ┌─┴─┐
  161.                  (O)─┘          └─(O)
  162.                   │                │
  163.                 ┌─┴─┐            ┌─┴─┐
  164.              (O)┘   └(O)      (O)┘   └(O)
  165.             ┌─┴─┐   ┌─┴─┐    ┌─┴─┐   ┌─┴─┐
  166.             │   │   │   │    │   │   │   │
  167.             b1 ~b1  b2 ~b1  ~b1 ~b2  b2 ~b2    Random Connections
  168.                                ┌──────┬──────┐
  169.                                │ ~b1  │ ~b2  │ Complements
  170.                                └──┬───┴──┬───┘
  171.                ┌──────────────────┘      │
  172.                │      ┌──────────────────┘
  173.             ┌──┴───┬──┴───┐
  174.             │  b1  │  b2  │ Input Vector
  175.             └──┬───┴──┬───┘
  176.           ┌────┴──────┴───┐
  177.           │  Random Walk  │
  178.           │    Encoder    │
  179.           └───┬───────┬───┘
  180.               │       │
  181.              X1       X2
  182.  
  183.          Figure 1: Using several trees to compute Y = ƒ(X1, X2)
  184.  
  185.                                     -2-
  186.  
  187. 2     Writing Applications With atree
  188. ~     ~~~~~~~ ~~~~~~~~~~~~ ~~~~ ~~~~~
  189.  
  190. Writing applications that perform a simple classification (yes or no) is
  191. relatively easy (within the constraints of Windows programming). The
  192. programmer creates a training set, then creates a tree using atree_create.
  193. The tree is trained using atree_train and then it can be used to evaluate
  194. new inputs using atree_eval. Examples of this can be seen in the files
  195. mosquito.c, and mult.c, both of which hide most of Windows' dressings
  196. for clarity.
  197.  
  198. Writing applications where the tree has to learn real number valued
  199. functions is a little more complex, as the programmer has to come to grips
  200. with the encoding problem.
  201.  
  202. Because a single tree produces only one bit, the programmer must train
  203. several trees on the input data, each one responsible for one bit of the
  204. output data. This is made slightly simpler by the choice of parameters
  205. for atree_train() which takes an array of bit vectors as the training set,
  206. and an array of bit vectors for the result set. The programmer provides
  207. an integer which states which bit column of the result set the current tree
  208. is being trained on. Typical code might look as follows:-
  209. ....
  210. {
  211.     int i;
  212.     int j;
  213.     LPBIT_VEC train;   /* LPBIT_VEC is a long (far) pointer to a bit_vec */
  214.     LPBIT_VEC result;
  215.     LPATREE *forest;   /* LPATREE is a long (far) pointer to an atree */
  216.  
  217.     /* Create the training set */
  218.     train = domain();
  219.  
  220.     /* Create the result set */
  221.